package com.leetcode.algorithm.y19.m04;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;

import com.leetcode.algorithm.common.TreeNode;

/**
 * leetcode-cn.com 
 * Map专题:
 * (done)387. 字符串中的第一个唯一字符
 * (done)49. 字母异位词分组
 * (done)36. 有效的数独
 * (TODO)652. 寻找重复的子树
 * 
 * @author: jie.deng
 * @time: 2019年4月30日 下午4:12:14
 */
public class MySolution0430 {
    
    /**
     * 387. 字符串中的第一个唯一字符
     * 给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。
     * 
     * 案例:
     * s = "leetcode" 返回 0.
     * s = "loveleetcode", 返回 2.
     * 
     * 注意事项：您可以假定该字符串只包含小写字母。
     * 
     * @param s
     * @return
     */
    public int firstUniqChar(String s) {
        if (s == null || s.length() == 0) {
            return -1;
        }
        Map<Character, Integer> map = new LinkedHashMap<Character, Integer>(); // key为字符，value为索引
        boolean[] isRepeated = new boolean[26];
        int len = s.length();
        for (int i = 0; i < len; i++) {
            char ch = s.charAt(i);
            if (isRepeated[ch - 'a']) {
                continue;
            }
            if (map.containsKey(ch)) {
                isRepeated[ch - 'a'] = true;
                map.remove(ch); // 移除重复的字符
                continue;
            }
            map.put(ch, i); // 记录每个字符第一次出现的索引
        }
        if (map.size() > 0) {
            return map.entrySet().iterator().next().getValue();
        }
        return -1;
    }
    
    
    /**
     * 49. 字母异位词分组
     * 
     * 给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
     * 
     * 示例:
     * 
     * 输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
     * 输出:
     * [
     *   ["ate","eat","tea"],
     *   ["nat","tan"],
     *   ["bat"]
     * ]
     * 说明：
     * 
     * 所有输入均为小写字母。
     * 不考虑答案输出的顺序。
     * @param strs
     * @return
     */
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for (String str : strs) {
            char[] chs = str.toCharArray();
            Arrays.sort(chs);
            String sortedStr = new String(chs);
            List<String> list = map.get(sortedStr);
            if (list == null) {
                list = new ArrayList<String>();
                // 当字符串/数组中每个元素的顺序不重要时，可以使用排序后的字符串 / 数组作为键。
                map.put(sortedStr, list);
            }
            list.add(str);
        }
        return new ArrayList<List<String>>(map.values());
    }
    
    
    /**
     * 36. 有效的数独
     * 
     * 判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
     * 
     * 数字 1-9 在每一行只能出现一次。
     * 数字 1-9 在每一列只能出现一次。
     * 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
     * 
     * 
     * 上图是一个部分填充的有效的数独。
     * 
     * 数独部分空格内已填入了数字，空白格用 '.' 表示。
     * 
     * 示例 1:
     * 
     * 输入:
     * [
     *   ["5","3",".",".","7",".",".",".","."],
     *   ["6",".",".","1","9","5",".",".","."],
     *   [".","9","8",".",".",".",".","6","."],
     *   ["8",".",".",".","6",".",".",".","3"],
     *   ["4",".",".","8",".","3",".",".","1"],
     *   ["7",".",".",".","2",".",".",".","6"],
     *   [".","6",".",".",".",".","2","8","."],
     *   [".",".",".","4","1","9",".",".","5"],
     *   [".",".",".",".","8",".",".","7","9"]
     * ]
     * 输出: true
     * 示例 2:
     * 
     * 输入:
     * [
     *   ["8","3",".",".","7",".",".",".","."],
     *   ["6",".",".","1","9","5",".",".","."],
     *   [".","9","8",".",".",".",".","6","."],
     *   ["8",".",".",".","6",".",".",".","3"],
     *   ["4",".",".","8",".","3",".",".","1"],
     *   ["7",".",".",".","2",".",".",".","6"],
     *   [".","6",".",".",".",".","2","8","."],
     *   [".",".",".","4","1","9",".",".","5"],
     *   [".",".",".",".","8",".",".","7","9"]
     * ]
     * 输出: false
     * 解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。
     *      但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
     * 说明:
     * 
     * 一个有效的数独（部分已被填充）不一定是可解的。
     * 只需要根据以上规则，验证已经填入的数字是否有效即可。
     * 给定数独序列只包含数字 1-9 和字符 '.' 。
     * 给定数独永远是 9x9 形式的。
     * @param board
     * @return
     */
    public boolean isValidSudoku(char[][] board) {
        Set<Character>[] rowSetArr = new Set[9];
        Set<Character>[] colSetArr = new Set[9];
        Set<Character>[] blockSetArr = new Set[9];
        for (int row = 0; row < 9; row++) {
            for (int col = 0; col < 9; col++) {
                if (board[row][col] != '.') {
                    Character ch = board[row][col];
                    if (rowSetArr[row] == null) {
                        rowSetArr[row] = new HashSet<Character>();
                    } else if (rowSetArr[row].contains(ch)) {
                        return false;
                    }
                    rowSetArr[row].add(ch);

                    if (colSetArr[col] == null) {
                        colSetArr[col] = new HashSet<Character>();
                    } else if (colSetArr[col].contains(ch)) {
                        return false;
                    }
                    colSetArr[col].add(ch);

                    if (blockSetArr[row / 3 * 3 + col / 3] == null) {
                        blockSetArr[row / 3 * 3 + col / 3] = new HashSet<Character>();
                    } else if (blockSetArr[row / 3 * 3 + col / 3].contains(ch)) {
                        return false;
                    }
                    blockSetArr[row / 3 * 3 + col / 3].add(ch);
                }
            }
        }
        return true;
    }
    
    /**
     * 652. 寻找重复的子树
     * 
     * 给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。
     * 
     * 两棵树重复是指它们具有相同的结构以及相同的结点值。
     * 
     * 示例 1：
     * 
     *         1
     *        / \
     *       2   3
     *      /   / \
     *     4   2   4
     *        /
     *       4
     * 下面是两个重复的子树：
     * 
     *       2
     *      /
     *     4
     * 和
     * 
     *     4
     * 因此，你需要以列表的形式返回上述重复子树的根结点。
     * @param root
     * @return
     */
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        return null;
    }
}
